The Twofish Encryption Algorithm: A 128-Bit Block Cipher The Twofish Encryption Algorithm: A 128-Bit Block Cipher
by Bruce Schneier ; John Kelsey ; Doug Whiting ; David Wagner ; Chris Hall ; Niels Ferguson
Wiley Computer Publishing, John Wiley & Sons, Inc.
ISBN: 0471353817   Pub Date: 03/01/99
  

Previous Table of Contents Next


The test was run on several Pentium computers with various amounts of RAM over a period of about ten days. The results showed that, for each of the four S-boxes, all NF mappings have a unique lsb sequence. Thus, each F function is unique for each distinct value of S.

8.4 Properties of the Key Schedule and Cipher

One NIST requirement is that the AES candidates have no weak keys. Here we argue that Twofish has none.

8.4.1 Equivalent Keys

A pair of equivalent keys, M, M*, is a pair of keys that encrypts all plaintexts into the same ciphertexts. We are almost certain that there are no equivalent keys in Twofish. As shown in section 8.1.2, there is no pair of keys, M, M*, that gives the same subkey sequence {Ki}. Section 8.3 showed that for two keys to generate the same round function in any one round, they must generate the same S.

It is conceivable that different sequences of subkeys and different S-boxes in g could end up producing the same encryption function, thus giving equivalent keys. This appears to be extremely unlikely, but we cannot prove that such equivalent keys do not exist.

A Conjecture about Equivalent Keys in Twofish. We conjecture that there are no pairs of Twofish keys that lead to identical encryptions for all inputs.

8.4.2 Self-Inverse Keys

Self-inverse keys are keys for which encrypting a block of data twice with the same key gives back the original data. We do not believe that self-inverse keys exist for Twofish. Keys cannot generate a self-inverse sequence of subkeys, because the same round subkey value can never appear more than once in the cipher. Again, it is conceivable that some keys axe self-inverse despite using different subkeys at different points, but again this is extremely unlikely. Self-inverse DES keys are sometimes referred to as “weak keys.”3


3The term “weak key” is used in conflicting ways in the literature. DES’ weak keys are fundamentally different from the weak keys of IDEA or Blowfish.

8.4.3 Pairs of Inverse Keys

A pair of inverse keys is a pair of keys M0, M1 such that EM0(EM1(X)) = X, for all X. We cannot see any way for this to occur. Encryption and decryption are slightly different processes, because of the one-bit rotations, so even if M0, M0, generate a pair of subkey sequences that are reversed, we still do not get pairs of inverse keys.

Consider a Twofish variant without those one-bit rotations. Can we find M0, M1, that lead to reversed subkey sequences? That is, can we find a pair of keys whose subkeys appear in the opposite position—the pre-XOR subkeys for M0 are the post-XOR subkeys for M1, the first round subkeys for M0 are the last round subkeys for M1, etc. To get reversed subkeys, we need to get reversed byte sequences from each of the eight byte-wide key-scheduling S-boxes. Finding a pair of byte sequences that are one another’s reverse sequences is the same difficulty as finding a collision in the whole byte sequence, and thus the same difficulty as finding a difference sequence in all 20 output byte positions. By the same arguments as we used above regarding difference sequences, then, this kind of reversed subkey sequence almost certainly doesn’t exist for any pair of keys M0, M1. For these reasons, we do not believe that there are pairs of inverse keys for Twofish. Note that pairs of inverse keys in DES are sometimes referred to as “semi-weak keys.”

8.4.4 Simple Relations

A key complementation property exists when

EM (P) = CEM´ (P´) = C´

where P´, C´, and K´ are the bitwise complement of P, C, and K, respectively. No such property has been observed for Twofish.

More generally, a simple relation [Knu94b] is defined as

EM (P) = CEf(M)´ (g(P,M))= h(C, M)

where f, g, and h are simple functions. We have found no simple relations for Twofish, and strongly doubt that they exist.

8.5 Key-dependent Characteristics and Weak Keys

The concept of a key-dependent characteristic seems to have been introduced in [BB93] in their cryptanalysis of Lucifer, and also appears in [DGV94a] in an analysis of IDEA.4 The idea is that certain iterative properties of the block cipher useful to an attacker become more effective against the cipher for a specific subset of keys.


4See [Haw98] for further cryptanalysis of IDEA weak keys.

A differential attack on Twofish may consider XOR-based differences, additive differences, or both. If an attacker sends XOR differences through the PHT and subkey addition steps, his differential characteristic probabilities will be dependent on the subkey values involved. In general, low-weight sub-keys will give an attacker some advantage, but this advantage is relatively small. (Zero bits in the subkeys improve the probabilities of cleanly getting XOR-based differential characteristics through the subkey addition.) Since there appears to be no special way to choose the key to make the subkey sequence especially low weight, we do not believe this kind of key-dependent differential characteristic will have any relevance in attacking Twofish.

A much more interesting issue in terms of key-dependent characteristics is whether the key-dependent S-boxes are ever generated with especially high-probability differential or high-bias linear characteristics. The statistical analysis presented earlier shows that the best linear and differential characteristics over all possible keys are still quite unlikely.

Note that the structure of both differential and linear attacks in Twofish is such that such attacks appear to generally require good characteristics through at least three of the four key-dependent S-boxes (if not all four), so a single high-probability differential or linear characteristic for one S-box will not create a weakness in the cipher as a whole.

8.6 Reed-Solomon Code

The RS structure helps defend against many possible related-key attacks by diffusing the key material in a direction “orthogonal” to the flow used in computing the 8-by-8-bit S-boxes of Twofish. For example, a single byte change in the key is guaranteed to affect all four key-dependent S-boxes in g. Since RS codes are MDS [MS77], the minimum number of different bytes between distinct 12-byte vectors generated by the RS code is guaranteed to be at least five. Notice that any attempt in a related-key attack to affect only a single byte in the computation of A or B is guaranteed to affect all four bytes in the computation of T0 and Ti. The S-box keys are used in reverse order from the associated key bytes so that related-key material is used in a different order in the round function than in the subkey generation.

The reversible RS code used in Twofish was chosen via computer search to minimize implementation cost. The code generator polynomial is

where α is a root of the primitive polynomial w(x) used to define the field.

Because all of these coefficients are “simple,” this RS computation is easily performed with no tables, using only a few shifts and XOR operations; this is particularly attractive for smart cards and hardware implementations. This computation is only performed once per key schedule setup per 64 bits of key, so the concern in choosing an RS code with such simple coefficients was not the performance overhead, but saving ROM space or gates. Precomputing the RS remainders requires only eight bytes of RAM on a smart card for 128-bit keys.

To take advantage of the simple coefficients of the polynomial, the RS matrix multiply should not be implemented as a direct matrix multiply but as a loop over the input bytes, where each iteration uses the coefficients of the polynomial once.


Previous Table of Contents Next